As it is known by the man skilled in the art, it may occur that data be lost or corrupted during their transmission between communication equipments. In this case the receiver may require from the sender that it transmits again the lost or corrupted data, or two copies of the data may be initially transmitted. Another solution consists in encoding the data to be transmitted by means of codes and more precisely erasure correcting codes. In this case, it is not necessary to wait having received every data of a content to be able to decode them, because only a (sufficient) part of these content data is required to rebuild all the data transmitted by the sender.
Among the encoding method the one named “network coding” offers several advantages. This encoding method has been proposed by Rudolf Ahlswede and al, in “Network information flow”, IEEE Transactions On Information Theory 2000. It may be used in wireless and/or internet networks, for instance. Network coding allows internal (or intermediate) routers of a network to send combinations of data of the type c=f(a,b) when it receives data a and b, instead of only forwarding the received data a or b. So, network coding allows reaching a maximal flow over a network whereas routing appears to be not powerful enough to reach a maximal flow in some networks. But this requires that routers be capable of performing computation on the received data to encode them before transmitting them, and that each final receiver be capable of decoding the encoded data it receives.
As computing the set of functions f( ) that allows to reach a maximal flow is proven to be NP-Hard, some probabilistic schemes have been proposed.
For instance, a scheme using rateless random linear network codes (RLNC) has been proposed by T. Ho and al, in “A random linear network coding approach to multicast”, IEEE Transaction on Information Theory 2006. This scheme has several advantages: it is rather simple to implement and can be fully distributed. According to this scheme, each router of a network forwards a random linear combination of the data it receives (inputs) to the other routers of its network. The receiver also receives a matrix of coefficient and data that allow it to decode the received data through a Gauss or Gauss-Jordan elimination when this matrix is invertible.
Network coding allowing to generate symbols independently, infinite is streams of symbols can be generated. However, random linear network codes involve complex computations not only during encoding but also during decoding. Moreover, as the RLNCs operate on the Gallois Field GF(2k), they are not suitable for encoding and decoding over general purpose processors that lack arithmetic on finite fields.
Another scheme, using Raptor codes, has been proposed by N. Thomos and P. Frossard, in “Collaborative video streaming with Raptor network coding”, ICME 2008. This scheme introduces a re-encoding method consisting in combining encoded symbols of a pair by means of a XOR Boolean operation. But, this scheme also requires Gaussian elimination during decoding, and therefore a raptor network coding loses its advantages in term of performance and properties.
Another scheme has also been proposed by Puducheri S. et al. in “Coding Schemes for an erasure relay channel” Proc. IEEE International Symposium on Information Theory, ISIT 2007, 24 Jun. 2007, pages 666-670.